package com.fulin.datastract.huisu;

import com.alibaba.druid.support.json.JSONUtils;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Description ”组合和“算法，每个元素只能用一次,搜索路径是一颗树，高度从左到右依次降低
 *  [1,2,4,6]
 *
 * @Author fulin16
 * @Date 2020/9/26 10:47
 **/
public class CombinationSum{

    private static List<List<Integer>> graph = new ArrayList<List<Integer>>();

    private static int[] candidates = {2,3,5,1,6,7,9,10,20,40,8,4,90,18,17,15};

    private static int target = 35;

    public static void main(String[] args) {
        Arrays.sort(candidates);
        CombinationSum com = new CombinationSum();
        com.combinationSum(candidates,target);
        System.out.println("size : " +graph.size());
    }

    private void combinationSum(int[] candidates, int target) {
        ArrayList<Integer> path = new ArrayList<>();
        for(int i = 0; i< candidates.length;i++){
            if(candidates[i] > target){
                return;
            }else{
                combination(path,candidates,target,0,i);
                path.remove(path.size() -1);
            }
        }
    }

    private void combination(List<Integer> path, int[] candidates,int target,int sum,int start){
        if(start == candidates.length){
            return;
        }
        path.add(candidates[start]);
        sum = sum + candidates[start];
        if(sum > target){
            return;
        }

        if(sum == target){
            System.out.println(JSONUtils.toJSONString(path));
            graph.add(path);
            return;
        }

        for(int i = start + 1 ; i < candidates.length; i++){
            combination(path,candidates,target,sum,i);
            path.remove(path.size() -1);
        }
    }
}
